package Linklist;

public class MyLinkList {

    static class LinkNode {
        public int val;
        public LinkNode next;

        public LinkNode(int val) {
            this.val = val;
        }
    }

    public LinkNode head;

    /*public void createList() {
        LinkNode node1 = new LinkNode(1);
        LinkNode node2 = new LinkNode(2);
        LinkNode node3 = new LinkNode(3);
        LinkNode node4 = new LinkNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        this.head = node1;
    }*/

    public void show() {
        LinkNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }

    }

    public int size() {
        LinkNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    //是否包含 数据key

    public boolean contains(int key) {
        LinkNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data) {
        LinkNode node = new LinkNode(data);
        node.next = head;
        head = node;
    }

    //尾插法
    public void addLast(int data) {
        LinkNode node = new LinkNode(data);
        if (head == null) {
            head = node;
            return;
        }
        LinkNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    public void addIndex(int index, int val) /*throws RuntimeException*/ {
        if (index < 0 || index > size()) {
            //throw new RuntimeException("inedx不合法");
            return;
        }
        LinkNode node = new LinkNode(val);
        if (head == null) {
            head = node;
            return;
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }

        LinkNode cur = head;

        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
    }

    public void addIndex1(int index, int val) /*throws RuntimeException*/ {
        if (index < 0 || index > size()) {
            //throw new RuntimeException("inedx不合法");
            return;
        }

        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }

        LinkNode node = new LinkNode(val);
        LinkNode cur = findIndex(index);

        node.next = cur.next;
        cur.next = node;

    }

    public LinkNode findIndex(int index) {
        int count = 0;
        LinkNode cur = head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    public LinkNode findMiddleNode1() {
        int len = size();
        LinkNode cur = head;
        int count = 0;
        while (count != len / 2) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    public LinkNode findMiddleNode() {
        LinkNode slow = head;
        LinkNode fast = head;

        while (fast != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public int kthToLast2(int k) {
        if (head == null || k < 0 || k > size()) {
            return -1;
        }

        int len = size();
        int count = 0;
        LinkNode cur = head;

        while (count != len - k) {
            cur = cur.next;
            count++;
        }
        return cur.val;
    }

    public int kthToLast3(int k) {
        if (head == null || k < 0 || k > size()) {
            return -1;
        }

        LinkNode slow = head;
        LinkNode fast = head;

        while (k - 1 != 0) {
            fast = fast.next;
            k--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    /*public LinkNode removeElements(int val) {
        if (head == null) {
            return null;
        }
        LinkNode cur = head;
        LinkNode prev = head;
        while (cur != null) {
            cur = cur.next;
            if (cur.val == val) {
                if (cur.next==null){
                    prev.next=null ;
                }
                else {
                    prev = cur.next;
                    cur = prev;
                }

            }
            prev = cur;
        }
        if (cur.next == null) {
            prev.next = null;
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }*/

    public LinkNode removeElements(int val) {
        if (head == null) {
            return null;
        }
        LinkNode cur = head.next;
        LinkNode prev = head;

        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = prev.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }


    public LinkNode reverseList() {
        if (head == null) {
            return null;
        }

        LinkNode cur = head.next;
        head.next = null;

        while (cur != null) {
            LinkNode prev = cur.next;
            cur.next = head;
            head = cur;
            cur = prev;
        }
        return head;
    }

    public LinkNode middleNode() {
        if (head == null) {
            return null;
        }

        LinkNode slow = head;
        LinkNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return head;
    }

    public int kthToLast(int k) {
        if (head == null) {
            return -1;
        }
        LinkNode fast = head;
        LinkNode slow = head;
        while (k - 1 != 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;

        }
        return slow.val;
    }

    public LinkNode mergeTwoLists1(LinkNode list1, LinkNode list2) {
        if (list1 == null || list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        LinkNode cur1 = list1;
        LinkNode cur2 = list2;
        LinkNode prev1 = list1.next;
        LinkNode prev2 = list2.next;

        while (prev1 != null && prev2 != null) {
            if (cur1.val == cur2.val) {
                cur1.next = cur2;
                cur1 = prev1;
                cur2 = prev2;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
            if (cur1.val > cur2.val) {
                cur2.next = cur1;
                cur2 = prev2;
                cur1 = prev1;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
            if (cur1.val < cur2.val) {
                cur1.next = cur2;
                cur1 = prev1;
                cur2 = prev2;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
        }
        while (cur1.val > cur2.val) {
            cur2.next = cur1;
        }

        while (cur1.val < cur2.val) {
            cur1.next = cur2;
        }
        return list1.val < list2.val ? list1 : list2;
    }

    public LinkNode mergeTwoLists(LinkNode list1, LinkNode list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        LinkNode cur1 = list1;
        LinkNode cur2 = list2;
        LinkNode prev1 = list1.next;
        LinkNode prev2 = list2.next;

        while (prev1 != null && prev2 != null) {
            if (cur1.val == cur2.val) {
                cur1.next = cur2;
                cur1 = prev1;
                cur2 = prev2;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
            if (cur1.val > cur2.val) {
                cur2.next = cur1;
                cur2 = prev2;
                cur1 = prev1;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
            if (cur1.val < cur2.val) {
                cur1.next = cur2;
                cur1 = prev1;
                cur2 = prev2;
                prev1 = prev1.next;
                prev2 = prev2.next;
            }
        }
        while (cur1.val > cur2.val) {
            cur2.next = cur1;
        }

        while (cur1.val < cur2.val) {
            cur1.next = cur2;
        }
        return list1.val < list2.val ? list1 : list2;
    }

    public LinkNode partition(int x) {
        if (head == null) {
            return null;
        }
        LinkNode cur = head;
        LinkNode a1 = null;
        LinkNode a2 = null;
        LinkNode b1 = null;
        LinkNode b2 = null;

        while (cur != null) {
            if (cur.val < x) {
                if (a1 == null) {
                    a1 = a2 = cur;
                } else {
                    a2.next = cur;
                    a2 = a2.next;
                }
                cur = cur.next;
            } else {
                if (b1 == null) {
                    b1 = b2 = cur;
                } else {
                    b2.next = cur;
                    b2 = b2.next;
                }
                cur = cur.next;
            }
        }
        if (a1 == null) {
            return b1;
        }
        a2.next = b1;
        if (b2 != null) {
            b2.next = null;
        }

        return a1;
    }

    public boolean isPalindrome() {
        if (head == null) {
            return false;
        }

        LinkNode slow = head;
        LinkNode fast = head;
        int count = 0;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            count++;
        }
        LinkNode cur = slow.next;
        while (cur != null) {
            LinkNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        while (count != 0) {
            if (head.val == slow.val) {
                head = head.next;
                slow = slow.next;
                count--;
            } else {
                return false;
            }
        }
        return true;
    }


    public LinkNode getIntersectionNode(LinkNode headA, LinkNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int countA = 0;
        int countB = 0;
        LinkNode curA = headA;
        LinkNode curB = headB;
        while (curA != null) {
            curA = curA.next;
            countA++;
        }
        while (curB != null) {
            curB = curB.next;
            countB++;
        }
        curA = headA;
        curB = headB;
        if (countA > countB) {
            for (int i = 0; i < countA - countB; i++) {
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < countB - countA; i++) {
                curB = curB.next;
            }
        }
        while (curA != null && curB != null) {
            if (curA.val == curB.val) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    public boolean hasCycle() {
        if (head == null) {
            return false;
        }
        LinkNode curA = head;
        LinkNode curB = head;
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next.next;
            if (curA == curB) {
                return true;
            }
        }
        return false;
    }

    /*public boolean hasCycle(ListNode head) {
        if (head == null ) {
            return false;
        }
        ListNode curA = head;
        ListNode curB = head;
        while (curB != null && curB.next != null) {
            curA = curA.next;
            curB = curB.next.next;
            if (curA == curB) {
                return true;
            }
        }
        return false;
    }*/

    public LinkNode detectCycle() {
        if (head == null) {
            return null;
        }
        LinkNode slow = head;
        LinkNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast==slow){
                break;
            }
        }
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
            if (fast==slow){
                return slow;
            }
        }
        return slow;
    }
}
